/* 
 * Copyright (c) 2009
 * Tencent soso better group
 * 
 * Author: sparkzheng@
 * Date: 2009-07-24
 * Desc: a basic segment-tree module for yaez_iprbl server
 * History:
 */

#include <stdlib.h>
#include <string.h>

#include "sgtree.h"

static inline void _sg_free_node(S_SGTREE_NODE *node, void *arg);
static inline int _sg_compare(in_addr_t ip, in_addr_t ip2_low, in_addr_t ip2_high);

static inline int _rb_compare(in_addr_t ip1_low, in_addr_t ip2_low);
static void _rb_rotate_left(S_SGTREE_HEAD *head, S_SGTREE_NODE *node);
static void _rb_rotate_right(S_SGTREE_HEAD *head, S_SGTREE_NODE *node);
static void _rb_insert_fixup(S_SGTREE_HEAD *head, S_SGTREE_NODE *node);
static void _rb_delete_fixup(S_SGTREE_HEAD *head, S_SGTREE_NODE *node);
static void _rb_inorder(S_SGTREE_NODE *node, SG_WALKER_FN walker, void *arg);
static void _rb_postorder(S_SGTREE_NODE *node, SG_WALKER_FN walker, void *arg);
static void _rb_preorder(S_SGTREE_NODE *node, SG_WALKER_FN walker, void *arg);

static int _rb_insert(S_SGTREE_HEAD *head, S_SGTREE_NODE *node);
static S_SGTREE_NODE *_rb_delete(S_SGTREE_HEAD *head, S_SGTREE_NODE *node);
static S_SGTREE_NODE *_rb_find(S_SGTREE_NODE *node, in_addr_t ip,
			       SG_STRATEGY_T type);

/* sg_leaf: global node sg_leaf */
S_SGTREE_NODE sg_leaf = {
	&sg_leaf,
	&sg_leaf,
	&sg_leaf,
	SG_BLACK,
	0,
	0
};

/* sg functions */
static inline void _sg_free_node(S_SGTREE_NODE *node, void *arg)
{
	(void)arg;
	free(node);
	return;
}

static inline int _sg_compare(in_addr_t ip, in_addr_t ip2_low, in_addr_t ip2_high)
{
	if (ip < ip2_low) 
		return 1;
	else if (ip > ip2_high)
		return -1;
	else
		return 0;
}

/* rb functions */
static inline int _rb_compare(in_addr_t ip1_low, in_addr_t ip2_low)
{
	if (ip1_low == ip2_low) 
		return 0;
	else if (ip1_low < ip2_low)
		return -1;
	else
		return 1;
}

static void _rb_rotate_left(S_SGTREE_HEAD *head, S_SGTREE_NODE *node)
{
	S_SGTREE_NODE *temp;

	temp = SG_RIGHT(node);
	SG_RIGHT(node) = SG_LEFT(temp);
	if (SG_LEFT(temp) != &sg_leaf) {
		SG_PARENT(SG_LEFT(temp)) = node;
	}

	SG_PARENT(temp) = SG_PARENT(node);

	if (SG_PARENT(node) == &sg_leaf) {
		SG_ROOT(head) = temp;
	} else {
		if (node == SG_LEFT(SG_PARENT(node))) {
			SG_LEFT(SG_PARENT(node)) = temp;
		} else {
			SG_RIGHT(SG_PARENT(node)) = temp;
		}
	}

	SG_LEFT(temp) = node;
	SG_PARENT(node) = temp;
	return;
}

static void _rb_rotate_right(S_SGTREE_HEAD *head, S_SGTREE_NODE *node)
{
	S_SGTREE_NODE *temp;

	temp = SG_LEFT(node);
	SG_LEFT(node) = SG_RIGHT(temp);
	if (SG_RIGHT(temp) != &sg_leaf) {
		SG_PARENT(SG_RIGHT(temp)) = node;
	}

	SG_PARENT(temp) = SG_PARENT(node);

	if (SG_PARENT(node) == &sg_leaf) {
		SG_ROOT(head) = temp;
	} else {
		if (node == SG_RIGHT(SG_PARENT(node))) {
			SG_RIGHT(SG_PARENT(node)) = temp;
		} else {
			SG_LEFT(SG_PARENT(node)) = temp;
		}
	}

	SG_RIGHT(temp) = node;
	SG_PARENT(node) = temp;
	return;
}

static void _rb_insert_fixup(S_SGTREE_HEAD *head, S_SGTREE_NODE *node)
{
	S_SGTREE_NODE *uncle;

	while (SG_IS_RED(SG_PARENT(node))) {
		if (SG_PARENT(node) == SG_LEFT(SG_PARENT(SG_PARENT(node)))) {
			uncle = SG_RIGHT(SG_PARENT(SG_PARENT(node)));
			if (SG_IS_RED(uncle)) {
				SG_SET_BLACK(SG_PARENT(node));
				SG_SET_BLACK(uncle);
				SG_SET_RED(SG_PARENT(SG_PARENT(node)));
				node = SG_PARENT(SG_PARENT(node));
			} else {
				if (node == SG_RIGHT(SG_PARENT(node))) {
					node = SG_PARENT(node);
					_rb_rotate_left(head, node);
				}
				SG_SET_BLACK(SG_PARENT(node));
				SG_SET_RED(SG_PARENT(SG_PARENT(node)));
				_rb_rotate_right(head,
						 SG_PARENT(SG_PARENT(node)));
			}
		} else {
			uncle = SG_LEFT(SG_PARENT(SG_PARENT(node)));
			if (SG_IS_RED(uncle)) {
				SG_SET_BLACK(SG_PARENT(node));
				SG_SET_BLACK(uncle);
				SG_SET_RED(SG_PARENT(SG_PARENT(node)));
				node = SG_PARENT(SG_PARENT(node));
			} else {
				if (node == SG_LEFT(SG_PARENT(node))) {
					node = SG_PARENT(node);
					_rb_rotate_right(head, node);
				}
				SG_SET_BLACK(SG_PARENT(node));
				SG_SET_RED(SG_PARENT(SG_PARENT(node)));
				_rb_rotate_left(head,
						SG_PARENT(SG_PARENT(node)));
			}
		}
	}

	SG_SET_BLACK(SG_ROOT(head));
	return;
}

static void _rb_delete_fixup(S_SGTREE_HEAD *head, S_SGTREE_NODE *node)
{
	S_SGTREE_NODE *sibling;

	while (node != SG_ROOT(head) && SG_IS_BLACK(node)) {
		if (node == SG_LEFT(SG_PARENT(node))) {
			sibling = SG_RIGHT(SG_PARENT(node));
			if (SG_IS_RED(sibling)) {
				SG_SET_BLACK(sibling);
				SG_SET_RED(SG_PARENT(node));
				_rb_rotate_left(head, SG_PARENT(node));
				sibling = SG_RIGHT(SG_PARENT(node));
			}

			if (SG_IS_BLACK(SG_LEFT(sibling)) &&
			    SG_IS_BLACK(SG_RIGHT(sibling))) {
				SG_SET_RED(sibling);
				node = SG_PARENT(node);
			} else {
				if (SG_IS_BLACK(SG_RIGHT(sibling))) {
					SG_SET_BLACK(SG_LEFT(sibling));
					SG_SET_RED(sibling);
					_rb_rotate_right(head, sibling);
					sibling = SG_RIGHT(SG_PARENT(node));
				}
				SG_COLOR(sibling) = SG_COLOR(SG_PARENT(node));
				SG_SET_BLACK(SG_PARENT(node));
				SG_SET_BLACK(SG_RIGHT(sibling));
				_rb_rotate_left(head, SG_PARENT(node));
				node = SG_ROOT(head);
			}
		} else {
			sibling = SG_LEFT(SG_PARENT(node));
			if (SG_IS_RED(sibling)) {
				SG_SET_BLACK(sibling);
				SG_SET_RED(SG_PARENT(node));
				_rb_rotate_right(head, SG_PARENT(node));
				sibling = SG_LEFT(SG_PARENT(node));
			}

			if (SG_IS_BLACK(SG_RIGHT(sibling)) &&
			    SG_IS_BLACK(SG_LEFT(sibling))) {
				SG_SET_RED(sibling);
				node = SG_PARENT(node);
			} else {
				if (SG_IS_BLACK(SG_LEFT(sibling))) {
					SG_SET_BLACK(SG_RIGHT(sibling));
					SG_SET_RED(sibling);
					_rb_rotate_left(head, sibling);
					sibling = SG_LEFT(SG_PARENT(node));
				}
				SG_COLOR(sibling) = SG_COLOR(SG_PARENT(node));
				SG_SET_BLACK(SG_PARENT(node));
				SG_SET_BLACK(SG_LEFT(sibling));
				_rb_rotate_right(head, SG_PARENT(node));
				node = SG_ROOT(head);
			}
		}
	} /* while */

	SG_SET_BLACK(node);
	return;
}

static int _rb_insert(S_SGTREE_HEAD *head, S_SGTREE_NODE *node)
{
	int flag = 0;
	int cmp = 0;
	S_SGTREE_NODE *cur;
	S_SGTREE_NODE *temp = &sg_leaf;

	if (head == NULL || node == NULL) return -1;

	cur = SG_ROOT(head);

	while (cur != &sg_leaf) {
		flag = 0;
		temp = cur;

		cmp = _rb_compare(node->ip_low, cur->ip_low);
		if (cmp < 0) { /* key[node] < key[cur] */
			flag = 1;
			cur = SG_LEFT(cur);
		} else if (cmp > 0) { /* key[node] > key[cur] */
			cur = SG_RIGHT(cur);
		} else { /* key[node] == key[cur] */
			return -10; /* this could not exist */
		}
	} /* end while */

	INIT_SG_NODE(node, temp, SG_RED);

	if (temp == &sg_leaf) { /* root == NULL */
		SG_ROOT(head) = node;
	} else {
		if (flag == 1) {
			SG_LEFT(temp) = node;
		} else {
			SG_RIGHT(temp) = node;
		}
	}

	_rb_insert_fixup(head, node);
	
	++SG_COUNT(head);

	return 0;
}

static S_SGTREE_NODE *_rb_delete(S_SGTREE_HEAD *head, S_SGTREE_NODE *node)
{
	S_SGTREE_NODE *ret;
	S_SGTREE_NODE *temp;
	SG_COLOR_T ret_color;

	if (head == NULL || node == NULL) return NULL;

	if (SG_LEFT(node) == &sg_leaf || SG_RIGHT(node) == &sg_leaf) {
		ret = node;
	} else {
		ret = sg_successor(node);
	}

	if (SG_LEFT(ret) != &sg_leaf) {
		temp = SG_LEFT(ret);
	} else {
		temp = SG_RIGHT(ret);
	}

	SG_PARENT(temp) = SG_PARENT(ret);

	if (SG_PARENT(ret) == &sg_leaf) {
		SG_ROOT(head) = temp;
	} else {
		if (ret == SG_LEFT(SG_PARENT(ret))) {
			SG_LEFT(SG_PARENT(ret)) = temp;
		} else {
			SG_RIGHT(SG_PARENT(ret)) = temp;
		}
	}

	ret_color = SG_COLOR(ret);

	if (ret != node) {
/* exchange the pointer or exchange the key-value of ret and node(by Spark) */
		SG_COLOR(ret) = SG_COLOR(node);

		SG_LEFT(ret) = SG_LEFT(node);
		if (SG_PARENT(SG_LEFT(node)) == node) {
			SG_PARENT(SG_LEFT(node)) = ret;
		}

		SG_RIGHT(ret) = SG_RIGHT(node);
		if (SG_PARENT(SG_RIGHT(node)) == node) {
			SG_PARENT(SG_RIGHT(node)) = ret;
		}

		SG_PARENT(ret) = SG_PARENT(node);
		if (SG_PARENT(node) == &sg_leaf) {
			SG_ROOT(head) = ret;
		}
		if (SG_LEFT(SG_PARENT(node)) == node) {
			SG_LEFT(SG_PARENT(node)) = ret;
		} else {
			SG_RIGHT(SG_PARENT(node)) = ret;
		}
	}

	if (ret_color == SG_BLACK) {
		_rb_delete_fixup(head, temp);
	}

	--SG_COUNT(head);

	return node;
}

static S_SGTREE_NODE *_rb_find(S_SGTREE_NODE *node, in_addr_t ip,
			       SG_STRATEGY_T type)
{
	int cmp = 0;
	S_SGTREE_NODE *ret = NULL;

	switch (type) {
	case SG_EXACT: /* find exact */
		cmp = _sg_compare(ip, node->ip_low, node->ip_high);
		while (node != &sg_leaf && cmp != 0) {
			if (cmp < 0) {
				node = SG_RIGHT(node);
			} else {
				node = SG_LEFT(node);
			}
			if (node != &sg_leaf) {
				cmp = _sg_compare(ip, node->ip_low, node->ip_high);
			}
		}
		if (node != &sg_leaf)
			ret = node;
		break;

	case SG_OBSCURE: /* find the follow */
		cmp = _sg_compare(ip, node->ip_low, node->ip_high);
		while (node != &sg_leaf && cmp != 0) {
			ret = node;
			if (cmp < 0) {
				node = SG_RIGHT(node);
			} else {
				node = SG_LEFT(node);
			}
			if (node != &sg_leaf) {
				cmp = _sg_compare(ip, node->ip_low, node->ip_high);
			}
		}
		if (node != &sg_leaf)
			ret = node;
		break;

	default:
		break;
	}

	return ret;
}

static void _rb_inorder(S_SGTREE_NODE *node, SG_WALKER_FN walker, void *arg)
{
	if (node != &sg_leaf) {
		_rb_inorder(SG_LEFT(node), walker, arg);
		if (walker != NULL) {
			(*walker)(node, arg);
		}
		_rb_inorder(SG_RIGHT(node), walker, arg);
	}

	return;
}

static void _rb_postorder(S_SGTREE_NODE *node, SG_WALKER_FN walker, void *arg)
{
	if (node != &sg_leaf) {
		_rb_postorder(SG_LEFT(node), walker, arg);
		_rb_postorder(SG_RIGHT(node), walker, arg);
		if (walker != NULL) {
			(*walker)(node, arg);
		}
	}

	return;
}

static void _rb_preorder(S_SGTREE_NODE *node, SG_WALKER_FN walker, void *arg)
{
	if (node != &sg_leaf) {
		if (walker != NULL) {
			(*walker)(node, arg);
		}
		_rb_preorder(SG_LEFT(node), walker, arg);
		_rb_preorder(SG_RIGHT(node), walker, arg);
	}

	return;
}

/* sg-tree APIs */
S_SGTREE_HEAD *sg_init(void)
{
	S_SGTREE_HEAD *head = NULL;

	head = (S_SGTREE_HEAD *)malloc(sizeof(*head));
	if (head != NULL) INIT_SG_HEAD(head);

	return head;
}

void sg_exit(S_SGTREE_HEAD *head)
{
	if (head == NULL) return;

	_rb_postorder(SG_ROOT(head), _sg_free_node, NULL);
	
	free(head);

	return;
}

S_SGTREE_NODE *sg_minimum(S_SGTREE_NODE *node)
{
	S_SGTREE_NODE *ret = node;

	if (node == NULL) return NULL;

	while (SG_LEFT(ret) != &sg_leaf) {
		ret = SG_LEFT(ret);
	}

	return ret;
}

S_SGTREE_NODE *sg_maximum(S_SGTREE_NODE *node)
{
	S_SGTREE_NODE *ret = node;

	if (node == NULL) return NULL;

	while (SG_RIGHT(ret) != &sg_leaf) {
		ret = SG_RIGHT(ret);
	}

	return ret;
}

S_SGTREE_NODE *sg_predecessor(S_SGTREE_NODE *node)
{
	S_SGTREE_NODE *ret;
	S_SGTREE_NODE *temp;

	if (node == NULL) return NULL;

	ret = SG_LEFT(node);

	if (ret != &sg_leaf) {
		return sg_maximum(ret);
	}

	ret = SG_PARENT(node);
	temp = node;
	while (ret != &sg_leaf && temp == SG_LEFT(ret)) {
		temp = ret;
		ret = SG_PARENT(ret);
	}

	return ret;
}

S_SGTREE_NODE *sg_successor(S_SGTREE_NODE *node)
{
	S_SGTREE_NODE *ret;
	S_SGTREE_NODE *temp;

	if (node == NULL) return NULL;

	ret = SG_RIGHT(node);

	if (ret != &sg_leaf) {
		return sg_minimum(ret);
	}

	ret = SG_PARENT(node);
	temp = node;
	while (ret != &sg_leaf && temp == SG_RIGHT(ret)) {
		temp = ret;
		ret = SG_PARENT(ret);
	}

	return ret;
}

int sg_insert(S_SGTREE_HEAD *head, in_addr_t ip_low,
	      in_addr_t ip_high)
{
	int ret = 0;

	S_SGTREE_NODE *low = NULL;
	S_SGTREE_NODE *high = NULL;
	S_SGTREE_NODE *tmp = NULL;
	S_SGTREE_NODE *bak = NULL;
	S_SGTREE_NODE *from = NULL;
	S_SGTREE_NODE *to = NULL;
	S_SGTREE_NODE *cur = NULL;
	S_SGTREE_NODE *pre = NULL;
	S_SGTREE_NODE *suc = NULL;

	if (head == NULL || ip_low > ip_high) return -1;


	if (SG_EMPTY(head)) {
		while ((tmp = (S_SGTREE_NODE *)malloc(sizeof(*tmp))) == NULL);
		tmp->ip_high = ip_high;
		tmp->ip_low = ip_low;
		ret = _rb_insert(head, tmp);
		

		return ret;
	}
	
	low = _rb_find(SG_ROOT(head), ip_low, SG_OBSCURE);

	if (ip_low != ip_high) { /* insert an ip-segment */
		high = _rb_find(SG_ROOT(head), ip_high, SG_OBSCURE);

		if (low == high) { /* ip-segment on single node */
			if (ip_high < low->ip_low) {
				pre = sg_predecessor(low);
				if (pre != &sg_leaf && pre->ip_high == ip_low - 1 &&
				    ip_high == low->ip_low - 1) {
					pre->ip_high = low->ip_high;
					low = _rb_delete(head, low);
					free(low);
				} else if (pre != &sg_leaf && pre->ip_high == ip_low - 1 &&
					   ip_high != low->ip_low - 1) {
					pre->ip_high = ip_high;
				} else if (ip_high == low->ip_low - 1) {
					low->ip_low = ip_low;
				} else {
					while ((tmp = (S_SGTREE_NODE *)malloc(sizeof(*tmp))) == NULL);
					tmp->ip_high = ip_high;
					tmp->ip_low = ip_low;
					ret = _rb_insert(head, tmp);


				}
			} else if (ip_low > high->ip_high) {
				suc = sg_successor(high);
				if (suc != &sg_leaf && suc->ip_low == ip_high + 1 &&
				    ip_low == high->ip_high + 1) {
					high->ip_high = suc->ip_high;
					suc = _rb_delete(head, suc);
					free(suc);
				} else if (suc != &sg_leaf && suc->ip_low == ip_high + 1 &&
					   ip_low != high->ip_high + 1) {
					suc->ip_low = ip_low;
				} else if (ip_low == high->ip_high + 1) {
					high->ip_high = ip_high;
				} else {
					while ((tmp = (S_SGTREE_NODE *)malloc(sizeof(*tmp))) == NULL);
					tmp->ip_high = ip_high;
					tmp->ip_low = ip_low;
					ret = _rb_insert(head, tmp);


				}
			} else if (ip_low < low->ip_low && ip_high > low->ip_high) {
				low->ip_low = ip_low;
				low->ip_high = ip_high;
			} else if (ip_low < low->ip_low && ip_high <= low->ip_high) {
				low->ip_low = ip_low;
			} else if (ip_low >= low->ip_low && ip_high > low->ip_high) {
				low->ip_high = ip_high;
			} else {
				return 1;
			}
		} else { /* need to handle multi-nodes */
			while ((tmp = (S_SGTREE_NODE *)malloc(sizeof(*tmp))) == NULL);

			if (ip_low < low->ip_low) {
				pre = sg_predecessor(low);
				if (pre != &sg_leaf && ip_low == pre->ip_high + 1) {
					from = pre;
					tmp->ip_low = pre->ip_low;
				} else {
					from = low;
					tmp->ip_low = ip_low;
				}
			} else if (ip_low > low->ip_high + 1) {
				from = sg_successor(low);
				tmp->ip_low = ip_low;
			} else {
				from = low;
				tmp->ip_low = low->ip_low;
			}

			if (ip_high > high->ip_high) {
				suc = sg_successor(high);
				if (suc != &sg_leaf && ip_high == suc->ip_low - 1) {
					to = sg_successor(suc);
					tmp->ip_high = suc->ip_high;
				} else {
					to = sg_successor(high);
					tmp->ip_high = ip_high;
				}
			} else if (ip_high < high->ip_low - 1) {
				to = high;
				tmp->ip_high = ip_high;
			} else {
				to = sg_successor(high);
				tmp->ip_high = high->ip_high;
			}

			cur = from;
			while(cur != to) { /* delete the interval nodes */
				bak = cur;
				cur = sg_successor(cur);
				bak = _rb_delete(head, bak);
				free(bak);
			}
			ret = _rb_insert(head, tmp);
			

		} /* end mutli-nodes */
	} else { /* insert single ip */
		if (ip_low < low->ip_low) {
			pre = sg_predecessor(low);
			if (pre != &sg_leaf && pre->ip_high == ip_low - 1 &&
			    ip_high == low->ip_low - 1) {
				pre->ip_high = low->ip_high;
				low = _rb_delete(head, low);
				free(low);
			} else if (pre != &sg_leaf && pre->ip_high == ip_low - 1 &&
				   ip_high != low->ip_low - 1) {
				pre->ip_high = ip_low;
			} else if (ip_high == low->ip_low - 1) {
				low->ip_low = ip_high;
			} else {
				while ((tmp = (S_SGTREE_NODE *)malloc(sizeof(*tmp))) == NULL);
				tmp->ip_high = ip_low;
				tmp->ip_low = ip_low;
				ret = _rb_insert(head, tmp);
			}
		} else if (ip_low > low->ip_high) {
			suc = sg_successor(low);
			if (suc != &sg_leaf && suc->ip_low == ip_high + 1 &&
			    ip_low == low->ip_high + 1) {
				low->ip_high = suc->ip_high;
				suc = _rb_delete(head, suc);
				free(suc);
			} else if (suc != &sg_leaf && suc->ip_low == ip_high + 1 &&
				   ip_low != low->ip_high + 1) {
				suc->ip_low = ip_high;
			} else if (ip_low == low->ip_high + 1) {
				low->ip_high = ip_low;
			} else {
				while ((tmp = (S_SGTREE_NODE *)malloc(sizeof(*tmp))) == NULL);
				tmp->ip_high = ip_high;
				tmp->ip_low = ip_low;
				ret = _rb_insert(head, tmp);
			}
		} else {
			ret = 1;
		}
	} /* end if single ip */

	return ret;
}

int sg_delete(S_SGTREE_HEAD *head, in_addr_t ip_low, in_addr_t ip_high)
{
	int ret = 0;
	
	S_SGTREE_NODE *low = NULL;
	S_SGTREE_NODE *high = NULL;
	S_SGTREE_NODE *tmp = NULL;
	S_SGTREE_NODE *from = NULL;
	S_SGTREE_NODE *to = NULL;
	S_SGTREE_NODE *cur = NULL;

	if (head == NULL || ip_low > ip_high) return -1;
	if (SG_EMPTY(head)) return 1;


	low = _rb_find(SG_ROOT(head), ip_low, SG_OBSCURE);

	if (ip_low != ip_high) { /* delete an ip-segment */
		high = _rb_find(SG_ROOT(head), ip_high, SG_OBSCURE);

		if (low == high) { /* ip-segment on single node */
			if (ip_high < low->ip_low) return 1;
			if (ip_low > low->ip_high) return 1;
			if (ip_low <= low->ip_low && ip_high >= low->ip_high) {
				low = _rb_delete(head, low);
				free(low);
			} else if (ip_low <= low->ip_low &&
				   ip_high < low->ip_high) {
				low->ip_low = ip_high + 1;
			} else if (ip_low > low->ip_low &&
				   ip_high >= low->ip_high) {
				low->ip_high = ip_low - 1;
			} else {
				while ((tmp = (S_SGTREE_NODE *)malloc(sizeof(*tmp)))
				       == NULL);
				tmp->ip_high = low->ip_high;
				tmp->ip_low = ip_high + 1;
				low->ip_high = ip_low - 1;
				ret = _rb_insert(head, tmp);


			}
		} else { /* need to handle multi-nodes */
			if (ip_low <= low->ip_low) {
				from = low;
			} else if (ip_low > low->ip_high) {
				from = sg_successor(low);
			} else {
				low->ip_high = ip_low - 1;
				from = sg_successor(low);
			}

			if (ip_high >= high->ip_high) {
				to = sg_successor(high);
			} else if (ip_high < high->ip_low) {
				to = high;
			} else {
				high->ip_low = ip_high + 1;
				to = high;
			}
		

			cur = from;
			while(cur != to) { /* delete the interval nodes */
				tmp = cur;
				cur = sg_successor(cur);
				tmp = _rb_delete(head, tmp);
				free(tmp);
			}
		} /* end if multi-nodes */
	} else { /* delete single ip */
		if (ip_low < low->ip_low) return 1;
		if (ip_low > low->ip_high) return 1;
		if (ip_low == low->ip_low && ip_low == low->ip_high) {
			low = _rb_delete(head, low);
			free(low);
		} else if (ip_low == low->ip_low && ip_low != low->ip_high) {
			low->ip_low++;
		} else if (ip_low != low->ip_low && ip_low == low->ip_high) {
			low->ip_high--;
		} else {
			while ((tmp = (S_SGTREE_NODE *)malloc(sizeof(*tmp))) == NULL);
			tmp->ip_high = low->ip_high;
			tmp->ip_low = ip_low + 1;
			low->ip_high = ip_low - 1;
			ret = _rb_insert(head, tmp);


		} 
	} /* end if single ip */

	return ret;
}

S_SGTREE_NODE *sg_find(S_SGTREE_HEAD *head, in_addr_t ip_low,
			      in_addr_t ip_high)
{
	S_SGTREE_NODE *low = NULL;
	S_SGTREE_NODE *high = NULL;

	if (head == NULL || ip_low > ip_high) return NULL;
	if (SG_EMPTY(head)) return NULL;
	
	low = _rb_find(SG_ROOT(head), ip_low, SG_EXACT);

	if (ip_low != ip_high) {	
		high = _rb_find(SG_ROOT(head), ip_high, SG_EXACT);

		if (low == high)
			return low;
		else
			return NULL;
	} 

	return low;
}

int sg_inorder(S_SGTREE_HEAD *head, SG_WALKER_FN walker, void *arg)
{
	S_SGTREE_NODE *cur;

	if (head == NULL) return -1;

	cur = SG_ROOT(head);
	_rb_inorder(cur, walker, arg);

	return 0;
}

int sg_postorder(S_SGTREE_HEAD *head, SG_WALKER_FN walker, void *arg)
{
	S_SGTREE_NODE *cur;

	if (head == NULL) return -1;

	cur = SG_ROOT(head);
	_rb_postorder(cur, walker, arg);

	return 0;
}

int sg_preorder(S_SGTREE_HEAD *head, SG_WALKER_FN walker, void *arg)
{
	S_SGTREE_NODE *cur;

	if (head == NULL) return -1;

	cur = SG_ROOT(head);
	_rb_preorder(cur, walker, arg);

	return 0;
}
